package 动态规划专项训练.动态规划训练2;

import java.util.Arrays;
import java.util.Comparator;

/**354. 俄罗斯套娃信封问题
 * @author zx
 * @create 2022-04-08 12:05
 */
public class Num354 {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0){
            return 0;
        }
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                //长度相等,宽度任意排序
                if(a[0] == b[0]){
                    return a[1] - b[1];
                }else{
                    //长度从小到大
                    return a[0] - b[0];
                }
            }
        });
        int n = envelopes.length;
        int[] f = new int[n];
        int res = 0;
        for(int i = 0;i < n;i++){
            f[i] = 1;
            for(int j = 0;j < i;j++){
                //信封 j 能被放进信封 i
                if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]){
                    f[i] = Math.max(f[i],f[j] + 1);
                }
            }
            res = Math.max(res,f[i]);
        }
        return res;
    }
}
